package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class IncreasingSubsequences {

	public static void main(String[] args) {
		IncreasingSubsequences object = new IncreasingSubsequences();
		int[] nums = {4, 3, 4, 1}; 
		System.out.println(object.findSubsequences(nums));
	}
	
    public List<List<Integer>> findSubsequences(int[] nums) {
    	List<List<Integer>> res = new ArrayList<List<Integer>>();
    	if(nums == null || nums.length <= 0){
    		return res;
    	}
    	Set<List<Integer>> set = new HashSet<List<Integer>>(); 
    	backtrack(nums, 0, set, new ArrayList<Integer>());
    	res = new ArrayList<>(set);
    	return res;
    }
    
    public void backtrack(int[] nums, int start, Set<List<Integer>> res, List<Integer> list){
    	if(list.size() >= 2){
    		res.add(new ArrayList<>(list));
    	}
    	for(int i = start; i < nums.length; i++){
    		if (!list.isEmpty() && nums[i] < list.get(list.size() - 1)) {
				continue;
			}
    		list.add(nums[i]);
    		backtrack(nums, i + 1, res, list);
    		list.remove(list.size() - 1);
    	}
    }
}
